#!/usr/bin/perl -w
#
# Calculate 24 (or N) points. Redundant expressions are eliminated.
#
# TODO : there may be bugs in constraints.

use strict;

my $EPSILON = 1e-8;

my $EXCHANGEABLE = 1;
my @OpSet = qw(+ - * / ^ _);

my %perlForm = (
                '+' => '+',
                '-' => '-',
                '*' => '*',
                '/' => '/',
                '^' => '**',
                '_' => '_',
                ''  => '' );
my %bCommutative = map(($_ => 1), qw(+ *));
my %Class = (
             '+' => 1,
             '-' => 1,
             '*' => 2,
             '/' => 2 );
my %Priority = (
                '+' => 1,
                '-' => 1,
                '*' => 2,
                '/' => 2,
                '^' => 3,
                '_' => 8,
                ''  => 9 );

my @ExprList;
my @LExprList;
my @RExprList;

@ARGV >= 3 or die "24p.pl object number1 number2 ...\n";

$EXCHANGEABLE ?
    P24_Exchangeable( @ARGV ) :
    P24_Stationary( @ARGV );

sub P24_Exchangeable {
    my ( $Target, $TotNumCnt ) = ($_[0], @_-1);
    my @Num = sort {$a <=> $b} @_[1..$TotNumCnt];
    my @Index = ( 0 .. $TotNumCnt-1 );
    my %bExist;
    my $x;

    do {  # Generate permutations :
        if ( !$bExist{ join( $;, @Num[@Index] ) } ) {
            $bExist{ join( $;, @Num[@Index] ) } = 1;
            P24_Stationary( $Target, @Num[@Index] );
        }
        $x = -1;
        for ( 0 .. $TotNumCnt-2 ) {
            $x = $_ if ( $Index[$_] <= $Index[$_+1] );
        }
        if ( $x > -1 ) {
            my $j;
            for ( $x .. $TotNumCnt-1 ) {
                $j = $_ if ( $Index[$x] <= $Index[$_] );
            }
            @Index[$x,$j] = @Index[$j,$x];
            for ( $x+1 .. $TotNumCnt-1 ) {
                @Index[$_, $TotNumCnt+$x-$_] = @Index[$TotNumCnt+$x-$_, $_];
                last if ( ($_+1)*2 > $TotNumCnt+$x );
            }
        }
    } while ( $x > -1 );
}

sub P24_Stationary {
    my ($Target, $TotNumCnt) = ($_[0], @_-1);
    my %ExprMap;
    $ExprMap{1, $_-1} = "::$_[$_]:$_[$_]" for ( 1..$TotNumCnt );
    # Op : LExpr : RExpr : Value

    for my $NumCnt (2 .. $TotNumCnt) {
        for my $StartNumNr ( 0..$TotNumCnt-$NumCnt ) {
            @ExprList = ();
            for my $LNumCnt ( reverse( 1..$NumCnt-1 ) ) {
                @LExprList = split( /;/,
                                    $ExprMap{$LNumCnt, $StartNumNr} );
                @RExprList = split( /;/,
                                    $ExprMap{$NumCnt-$LNumCnt, $StartNumNr+$LNumCnt} );
                CombineExprList();
            }
            $ExprMap{$NumCnt, $StartNumNr} = join( ';', @ExprList );
        }
    }
    @ExprList = split(/;/, $ExprMap{$TotNumCnt, 0});
    for my $OLRV ( @ExprList ) {
        my ( $Op, $LExpr, $RExpr, $Val ) = split( /:/, $OLRV );
        print "$LExpr$Op$RExpr = $Val\n" if ( abs($Val-$Target) < $EPSILON );
    }
}

sub CombineExprList {
    for my $Op (@OpSet) {
        for my $LOLRV (@LExprList) {    # LOLRV - Left Op:LExpr:RExpr:Value
            my ($LOp, $LLExpr, $LRExpr, $LVal) = split(/:/, $LOLRV);
            # only pure-number ods can be concatenated :
            next if ($Op eq '_' and $LOp ne '' and $LOp ne '_');

            my $LExpr = "$LLExpr$LOp$LRExpr";
            $LExpr = "($LExpr)" if ($Priority{$LOp} < $Priority{$Op});
            for my $ROLRV (@RExprList) {
                my ($ROp, $RLExpr, $RRExpr, $RVal) = split(/:/, $ROLRV);
                #               print "$LOp $Op $ROp\n";
                next if ($Op eq '_' and $ROp ne '');   # only pure-number ods can be concatenated
                next if ($Op eq '/' and $RVal == 1);   # A/1 folded into A*1
                next if ($Op eq '-' and $RVal == 0);   # A-0 folded into A+0
                next if (($Class{$Op} || -1) == ($Class{$ROp} || -2));  # C-(B+A) folded into C-B-A
                my $RExpr = "$RLExpr$ROp$RRExpr";
                $RExpr = "($RExpr)" if ($Priority{$ROp} <= $Priority{$Op});
                next if ($EXCHANGEABLE and ($Class{$LOp} || -1) == ($Class{$Op} || -2) and $LRExpr lt $RExpr);  # C-A-B folded into C-B-A
                next if ($EXCHANGEABLE and $bCommutative{$Op} and $LExpr lt $RExpr);    # A+B folded into B+A
                $RVal = "($RVal)" if ($RVal < 0);
                my $Value = eval("$LVal$perlForm{$Op}$RVal");
                next if ($@ or $Value eq '1.#INF');
                push(@ExprList, "$Op:$LExpr:$RExpr:$Value");
            }
        }
    }
}
